package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.HashMap;

/**
 * NC125 未排序数组中累加和为给定值的最长子数组长度
 *  算法知识视频讲解
 * 简单  通过率：42.43%  时间限制：2秒  空间限制：256M
 * 知识点
 * 哈希
 * 题目
 * 题解(2)
 * 讨论(12)
 * 排行
 * 描述
 * 给定一个无序数组arr, 其中元素可正、可负、可0。给定一个整数k，求arr所有子数组中累加和为k的最长子数组长度
 * 示例1
 * 输入：
 * [1,-2,1,1,1],0
 * 复制
 * 返回值：
 * 3
 * 复制
 * 备注：
 * \begin{array}{l}1 \leqslant N \leqslant 10^{5} \\ -10^{9} \leqslant k \leqslant 10^{9} \\ -100 \leqslant a r r_{i} \leqslant 100\end{array}
 * 1⩽N⩽10
 * 5
 *
 * −10
 * 9
 *  ⩽k⩽10
 * 9
 *
 * −100⩽arr
 * i
 * ​
 *  ⩽100
 * ​
 */
public class MaxLengthSum {

    @Test
    public void test() {
        System.out.println(maxlenEqualK(new int[]{1,-2,1,1,1}, 2));
    }

    public int maxlenEqualK (int[] arr, int k) {
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for (int i = 1; i < sum.length; ++i) {
            sum[i] = sum[i - 1] + arr[i];
        }
        for (int s = arr.length - 1; s >= 1; --s) {
            for (int i = 0; i + s < arr.length; ++i) {
                if (sum[i + s] - sum[i] + arr[i] == k) { // 计算从i到i + s 的和是否符合要求（从最长的长度开始找，有点贪心的意味）
                    return s + 1;
                }
            }
        }
        return 0;
    }
}
